#include <string>
#include <iostream>
#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H
using namespace std;
//Binary search tree
template<typename DTYPE>class BSTree
{
public:
    BSTree(const BSTree<DTYPE>& bstree);
    void add(const DTYPE& word);
    void print();
    void remove(const DTYPE& word);
    bool find(const DTYPE& word);
    BSTree();
    ~BSTree();
private:
    struct Tnode
    {
        DTYPE data;
        Tnode* left, *right;
    }*_head;
    BSTree(Tnode* head);
    static void DeleteNode(Tnode* node);
    static void PrintNode(Tnode* node);
};
template <typename DTYPE>
BSTree<DTYPE>::BSTree(const BSTree<DTYPE>& bstree)
{
    
}

BSTree(const BSTree<DTYPE>& bstree);
template<typename DTYPE>
bool BSTree<DTYPE>::find(const DTYPE& data)
{
    if(_head == NULL)
        return false;
    if(_head->data == data)
        return true;
    else if(_head->data < data){
        return BSTree(_head->right).find(data);
    }
    else{
        return BSTree(_head->left),find(data);
    }
}

template<typename DTYPE>
void BSTree<DTYPE>::remove(const DTYPE& data)
{
    cout << "BSTree::remove has been not implemented yet!" << endl;
}

//Non-Recursive Version
template<typename DTYPE>
void BSTree<DTYPE>::add(const DTYPE& data)
{
    if(0 == _head){
        _head = new Tnode();
        _head->data = data;
        _head->left = _head->right = 0;
    }else{
        Tnode* pnode = _head;
        for(;;){
            if(data == pnode->data){
                return;
            }
            else{
                Tnode** p = (data > pnode->data) ? &pnode->right:&pnode->left;
                if(*p == 0){
                    Tnode* newp = new Tnode();
                    newp->data = data;
                    newp->left = newp->right = 0;
                    *p = newp;
                    return;
                }else{
                    pnode = *p;
                }
            }
        }        
    }
}
template<typename DTYPE>
BSTree<DTYPE>::BSTree(Tnode* head):_head(head)
{
}
template<typename DTYPE>
BSTree<DTYPE>::BSTree():_head(0)
{
}
template<typename DTYPE>
BSTree<DTYPE>::~BSTree()
{
    //DeleteNode(_head);
}
template<typename DTYPE>
void BSTree<DTYPE>::print()
{
    PrintNode(_head);
}
template<typename DTYPE>
void BSTree<DTYPE>::DeleteNode(Tnode* node)
{
    if(node == 0){
        return;
    }
    else{
        DeleteNode(node->left);
        DeleteNode(node->right);
        delete node;
    }
}
template<typename DTYPE>
void BSTree<DTYPE>::PrintNode(Tnode* node)
{
    if(node == 0){
        return;
    }
    else{
        PrintNode(node->left);
        cout << node->data << std::endl;
        PrintNode(node->right);
    }
}
#endif
